/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package babydisco.Math;


import java.util.ArrayList;
import java.util.Arrays;

/**
 *  class that takes care of the fourier transform of all data
 * @author Florian
 */
public class Fourier
{

    private ArrayList<Double> input; //input data of measured voltages over time
    private double sampleFreq; // sample frequenty of the input
    private int sampleSize;
    private ArrayList<Complex> transformed; // fourier transformed input
    private ArrayList<Double> frequencies; // list of frequencies that correspond
                                           //to each X in the fourier transform
    private ArrayList<Double> amplitude;   // absolute value of the fourier transform


    public Fourier(ArrayList<Double> input, double sampleFreq)
    {

        quickfix(input);
        this.sampleFreq = sampleFreq;
        transformed = new ArrayList<Complex>();
        amplitude = new ArrayList<Double>();
        frequencies = new ArrayList<Double>();
        frequencies();
        fastTransform();
        constructAmplitude();
    }

    private void quickfix(ArrayList<Double> a){
        sampleSize = 1;
        int N= a.size();
        input = new ArrayList<Double>();
        while(sampleSize < N){
            sampleSize*=2;
        }
        if(sampleSize >N)
            sampleSize /=2;
        for(int i = 0;i<sampleSize;i++){
            this.input.add(a.get(i));
        }
    }

    /**
     * apply fourier on the input
     */
    private void transform()
    {
        Complex a = new Complex(0,0);
        Complex b = new Complex(0,0);
        double pi = Math.PI;
        for (int i = 0; i < sampleSize; i++)
        {
            //m is part of the fourier formula, given that I calculate it
            //2*samplesize times in the next for loop I decided to put it
            //here in hopes of getting some speed
            double m = (double) i/ sampleSize;
            a = new Complex(0, 0);
            for (int j = 0; j < sampleSize; j++)
            {
               b = new Complex( (double) input.get(j) * Math.cos(m * j * 2 * pi), -(double) input.get(j) * Math.sin(m * j * 2 * pi));
                a = Complex.add(a, b);
            }
            transformed.add(a);
        }
    }


    private void fastTransform(){
        Complex[] temp = new Complex[sampleSize];
        for(int i = 0; i < sampleSize;i++){
            temp[i] = new Complex(input.get(i),0);
        }

        Complex[] x = fft(temp);

        for(int i = 0; i< sampleSize;i++){
            transformed.add(x[i]);
        }
    

    }


     public static Complex[] fft(Complex[] x) {
        int N = x.length;
        // base case
        if (N == 1) {
            return new Complex[] {x[0]};
        }

        // radix 2 Cooley-Tukey FFT
        if (N % 2 != 0) { throw new RuntimeException("N is not a power of 2"); }

        // fft of even terms
        Complex[] even = new Complex[N/2];
        for (int k = 0; k < N/2; k++) {
            even[k] = x[2*k];
        }
  
      Complex[] q = fft(even);

        // fft of odd terms

       Complex[] odd  = even;  // reuse the array
        for (int k = 0; k < N/2; k++) {
            odd[k] =x[2*k+1];
        }
        Complex[] r = fft(odd);

        // combine
        Complex[] y = new  Complex[N];
        
        for (int k = 0; k < N/2; k++) {
            double kth = -2 * k * Math.PI / N;
          
            Complex wk = new Complex(Math.cos(kth), Math.sin(kth));
            y[k] = Complex.add(q[k],Complex.multiply(wk, r[k]));
           
            y[k+N/2]= Complex.subtract(q[k],Complex.multiply(wk, r[k]));
        }
        return y;

         
    }

    /**
     * construct the amplitude by taking the absolute value of the output
     * of the fourier transform
     */
    private void constructAmplitude(){
        for (int i =0;i< sampleSize;i++){
                amplitude.add(Complex.absolute(transformed.get(i)));
        }
    }

    /**
     * get the list of frequencies
     * @return arraylist of doubles
     */
    public ArrayList<Double> getFrequencies()
    {
        return frequencies;
    }

    /**
     * get the list of amplitudes
     * @return arraylist of doubles
     */
    public ArrayList<Double> getAmplitude(){
        return amplitude;
    }

    /**
     * get the complex output of the fourier transform
     * @return arraylist of complex numbers
     */
    public ArrayList<Complex> getTransformed()
    {
        return transformed;
    }

    /**
     * get the list of voltage inputs
     * @return list of doubles
     */
    public ArrayList<Double> getInput()
    {
        return input;
    }

    /**
     * get the sample size
     * @return int
     */
    public int getSampleSize()
    {
        return sampleSize;
    }

    /**
     * get the sample frequenty
     * @return double
     */
    public double getSampleFreq()
    {
        return sampleFreq;
    }
    /**
     * construct the list of frequencies corresponding to each complex fourier
     * value
     */
    private void frequencies()
    {
        for (double i = 0; i < sampleSize; i++)
        {
            frequencies.add(i * sampleFreq/ sampleSize);
          
        }
    }

    /**
     * print function for the list of complex numbers
     */
    public void print()
    {
        for (int i = 0; i < sampleSize; i++)
        {
            System.out.println(transformed.get(i).real + "  " + transformed.get(i).imaginair);
        }
    }
}
